package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * <p>
 * User:Mr.Du
 * Date:2024/4/25
 * Time:9:09
 */
public class CountCompleteComponents {

    int[] roots;
    int[] size;
    public int countCompleteComponents(int n, int[][] edges) {
        roots = new int[n];
        size = new int[n];
        for(int i = 0;i < n;i++){
            roots[i] = i;
            size[i] = 0;
        }
        for(int[] edge : edges){
            int x = edge[0], y = edge[1];
            this.union(x, y);
        }
        int res = 0;
        Map<Integer, Integer> mp = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i < n;i++){
            if(mp.containsKey(roots[i])){
                if(mp.get(roots[i]) == size[i]){
                    mp.put(roots[i], size[i]);
                }else{
                    mp.remove(roots[i]);
                    set.add(roots[i]);
                }
            }else{
                if(!set.contains(roots[i]))
                    mp.put(roots[i], size[i]);
            }
        }
        System.out.println(Arrays.toString(roots));
        System.out.println(Arrays.toString(size));
        return mp.size();
    }

    public int findRoot(int x){
        if(x == roots[x]) return x;
        return roots[x] = findRoot(roots[x]);
    }

    public void union(int x, int y){
        int p = findRoot(x);
        int q = findRoot(y);
        roots[q] = p;
        size[x]++;
        size[y]++;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0,1},{0,2},{1,2},{3,4}};
        System.out.println(new CountCompleteComponents().countCompleteComponents(5, edges));
    }
}
